#pragma once
#include<vector>
#include<stdio.h>
#include <iostream>
using namespace std;

class UnoinFindSet
{
public:
    //构造函数初始化;都为-1;
    UnoinFindSet(int size)
        :_set(size, -1)
    {}

    //给一个数找它的父结点;
    //由于下标是数, 而存放的值是结点;
    //父节点值特点就是是负数.
    size_t FindRoot(int x)
    {
        while(_set[x] >= 0)
        {
            x = _set[x];
        }
        return x;
    }

    //将两个数进行合并:
    //先找到两个数的根结点.
    void Union(int x1, int x2)
    {
        int root1 = FindRoot(x1);
        int root2 = FindRoot(x2);

        //判断两个数不是同一个集合.
        if(root1 != root2)
        {
            _set[root1] += _set[root2];
            _set[root2] = root1;
        }
    }

    //计算并查集中的根结点个数
    size_t SetCount()
    {
        size_t count = 0;
        for(size_t i = 0; i < _set.size(); i++)
        {
            if(_set[i] < 0)
                count++;
        }
        return count;
    }
private:
    std::vector<int> _set;
};


void TestUFS()
{
    UnoinFindSet u(10);

    u.Union(0, 6);
    u.Union(0, 7);
    u.Union(0, 8);

    u.Union(1, 4);
    u.Union(1, 9);

    u.Union(2, 3);
    u.Union(2, 5);

    cout << u.SetCount() << endl;
}